//链表进行加法运算
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head1 ListNode类
 * @param head2 ListNode类
 * @return ListNode类
 */
typedef struct ListNode ListNode;
ListNode* reverse_list(ListNode* head) {
    if (head == NULL)
        return NULL;
    if (head->next == NULL)
        return head;
    ListNode* n1 = NULL;
    ListNode* n2 = head;
    ListNode* n3 = head->next;
    while (n2) {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3 != NULL)
            n3 = n3->next;
    }
    return n1;
}
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    ListNode* _head1 = reverse_list(head1);
    ListNode* _head2 = reverse_list(head2);
    int count = 0;
    ListNode* new_head = (ListNode*)malloc(sizeof(ListNode));
    new_head->val = -1;
    new_head->next = NULL;
    ListNode* _new_head = new_head;
    while (_head1 && _head2) {
        ListNode* new = (ListNode*)malloc(sizeof(ListNode));
        new->val = _head1->val + _head2->val + count;
        new->next = NULL;
        if (new->val >= 10) {
            new->val = (new->val) % 10;
            count = 1;
        } else {
            count = 0;
        }
        _new_head->next = new;
        _new_head = _new_head->next;
        _head1=_head1->next;
        _head2=_head2->next;
    }
    while (_head1) {
        ListNode* new = (ListNode*)malloc(sizeof(ListNode));
        new->val = _head1->val  + count;
        new->next = NULL;
        if (new->val >= 10) {
            new->val = (new->val) % 10;
            count = 1;
        } else {
            count = 0;
        }
        _new_head->next = new;
        _new_head = _new_head->next;
        _head1=_head1->next;
    }
    while (_head2) {
        ListNode* new = (ListNode*)malloc(sizeof(ListNode));
        new->val =  _head2->val + count;
        new->next = NULL;
        if (new->val >= 10) {
            new->val = (new->val) % 10;
            count = 1;
        } else {
            count = 0;
        }
        _new_head->next = new;
        _new_head = _new_head->next;
        _head2=_head2->next;
    }
    if (count == 1) {
        ListNode* new = (ListNode*)malloc(sizeof(ListNode));
        new->val = count;
        new->next = NULL;
        if (new->val >= 10) {
            new->val = (new->val) % 10;
            count = 1;
        } else {
            count = 0;
        }
        _new_head->next = new;
        _new_head = _new_head->next;
    }
    return reverse_list(new_head->next);
}